{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Interval List Intersections"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: intervalIntersection"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #区间列表的交集"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个由一些<strong> 闭区间 </strong>组成的列表，<code>firstList</code> 和 <code>secondList</code> ，其中 <code>firstList[i] = [start<sub>i</sub>, end<sub>i</sub>]</code> 而 <code>secondList[j] = [start<sub>j</sub>, end<sub>j</sub>]</code> 。每个区间列表都是成对 <strong>不相交</strong> 的，并且 <strong>已经排序</strong> 。</p>\n",
    "\n",
    "<p>返回这 <strong>两个区间列表的交集</strong> 。</p>\n",
    "\n",
    "<p>形式上，<strong>闭区间</strong> <code>[a, b]</code>（其中 <code>a <= b</code>）表示实数 <code>x</code> 的集合，而 <code>a <= x <= b</code> 。</p>\n",
    "\n",
    "<p>两个闭区间的 <strong>交集</strong> 是一组实数，要么为空集，要么为闭区间。例如，<code>[1, 3]</code> 和 <code>[2, 4]</code> 的交集为 <code>[2, 3]</code> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/01/30/interval1.png\" style=\"width: 700px; height: 194px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]\n",
    "<strong>输出：</strong>[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>firstList = [[1,3],[5,9]], secondList = []\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>firstList = [], secondList = [[4,8],[10,12]]\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>firstList = [[1,7]], secondList = [[3,10]]\n",
    "<strong>输出：</strong>[[3,7]]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 <= firstList.length, secondList.length <= 1000</code></li>\n",
    "\t<li><code>firstList.length + secondList.length >= 1</code></li>\n",
    "\t<li><code>0 <= start<sub>i</sub> < end<sub>i</sub> <= 10<sup>9</sup></code></li>\n",
    "\t<li><code>end<sub>i</sub> < start<sub>i+1</sub></code></li>\n",
    "\t<li><code>0 <= start<sub>j</sub> < end<sub>j</sub> <= 10<sup>9</sup> </code></li>\n",
    "\t<li><code>end<sub>j</sub> < start<sub>j+1</sub></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [interval-list-intersections](https://leetcode.cn/problems/interval-list-intersections/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [interval-list-intersections](https://leetcode.cn/problems/interval-list-intersections/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,2],[5,10],[13,23],[24,25]]\\n[[1,5],[8,12],[15,24],[25,26]]', '[[1,3],[5,9]]\\n[]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        ans = []\n",
    "\n",
    "        for fs, fe in firstList:\n",
    "            for ss, se in secondList:\n",
    "                if ss > fe: break\n",
    "                if fs > se: continue\n",
    "                ans.append([max(fs, ss), min(fe, se)])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        ans = []\n",
    "\n",
    "        for fs, fe in firstList:\n",
    "            for ss, se in secondList:\n",
    "                if ss > fe: break\n",
    "                if fs > se: continue\n",
    "                ans.append([max(fs, ss), min(fe, se)])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        for i, j in firstList:\n",
    "            res.append([i, 1])\n",
    "            res.append([j, -1])\n",
    "        for i, j in secondList:\n",
    "            res.append([i, 1])\n",
    "            res.append([j, -1])     \n",
    "        res.sort(key = lambda x: (x[0], -x[1]))\n",
    "        print(res)\n",
    "        cur = 0\n",
    "        start = None\n",
    "        end = None\n",
    "        output = []\n",
    "        for i, j in res:\n",
    "            cur += j\n",
    "            if cur == 2:\n",
    "                if not start:\n",
    "                    start = i \n",
    "            if cur < 2 and start is not None:\n",
    "                end = i\n",
    "                output.append([start, end])\n",
    "                start = None\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        intersections = []\n",
    "        i, j = 0, 0\n",
    "        while i < len(firstList) and j < len(secondList):\n",
    "            l1,r1= firstList[i]\n",
    "            l2,r2= secondList[j]\n",
    "            if not (r1 < l2 or  r2 < l1):\n",
    "                intersections.append([max(l1,l2),min(r1,r2)])\n",
    "            if r1 > r2:\n",
    "                j += 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return intersections"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        for i, j in firstList:\n",
    "            res.append([i, 1])\n",
    "            res.append([j, -1])\n",
    "        for i, j in secondList:\n",
    "            res.append([i, 1])\n",
    "            res.append([j, -1])     \n",
    "        res.sort(key = lambda x: (x[0], -x[1]))\n",
    "        print(res)\n",
    "        cur = 0\n",
    "        start = None\n",
    "        end = None\n",
    "        output = []\n",
    "        for i, j in res:\n",
    "            cur += j\n",
    "            if cur == 2:\n",
    "                if not start:\n",
    "                    start = i \n",
    "            if cur < 2 and start is not None:\n",
    "                end = i\n",
    "                output.append([start, end])\n",
    "                start = None\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        tmp = []\n",
    "        for slot in firstList+secondList:\n",
    "            tmp.append([slot[0],1])\n",
    "            tmp.append([slot[1],-1])\n",
    "        tmp.sort(key = lambda x:[x[0],-x[1]])\n",
    "        count = 0\n",
    "        starttime = 0\n",
    "        rst = []\n",
    "        for time,i in tmp:\n",
    "            if count == 2:\n",
    "                rst.append([starttime,time])\n",
    "            count += i\n",
    "            if count == 2:\n",
    "                starttime = time\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        m,n=len(firstList),len(secondList)\n",
    "        ans=[]\n",
    "        l,r=0,0\n",
    "        while l<m and r<n:\n",
    "            le=max(firstList[l][0],secondList[r][0])\n",
    "            re=min(firstList[l][1],secondList[r][1])\n",
    "            if le<=re:\n",
    "                ans.append([le,re])\n",
    "            if firstList[l][1]<secondList[r][1]:\n",
    "                l+=1\n",
    "            else:\n",
    "                r+=1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        for first in firstList:\n",
    "            for second in secondList:\n",
    "                if first[0] <= second[0] and first[1] >= second[1]:\n",
    "                    res.append(second)\n",
    "                elif first[0] >= second[0] and first[1] <= second[1]:\n",
    "                    res.append(first)\n",
    "                elif first[0] < second[0] and first[1] > second[0] and first[1] < second[1]:\n",
    "                    res.append([second[0], first[1]])\n",
    "                elif first[0] > second[0] and first[0] < second[1] and first[1] > second[1]:\n",
    "                    res.append([first[0], second[1]])\n",
    "                elif first[0] == second[1]:\n",
    "                    res.append([first[0], first[0]]) \n",
    "                elif first[1] == second[0]:\n",
    "                    res.append([first[1], first[1]])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        i = j = 0\n",
    "\n",
    "        while i < len(firstList) and j < len(secondList):\n",
    "            lo = max(firstList[i][0], secondList[j][0])\n",
    "            hi = min(firstList[i][1], secondList[j][1])\n",
    "            if lo <= hi:\n",
    "                ans.append([lo, hi])\n",
    "\n",
    "            # Remove the interval with the smallest endpoint\n",
    "            if firstList[i][1] < secondList[j][1]:\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        for i, j in firstList:\n",
    "            res.append([i, 1])\n",
    "            res.append([j, -1])\n",
    "        for i, j in secondList:\n",
    "            res.append([i, 1])\n",
    "            res.append([j, -1])     \n",
    "        res.sort(key = lambda x: (x[0], -x[1]))\n",
    "        print(res)\n",
    "        cur = 0\n",
    "        start = None\n",
    "        end = None\n",
    "        output = []\n",
    "        for i, j in res:\n",
    "            cur += j\n",
    "            if cur == 2:\n",
    "                if not start:\n",
    "                    start = i \n",
    "            if cur < 2 and start is not None:\n",
    "                end = i\n",
    "                output.append([start, end])\n",
    "                start = None\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        res = list()\n",
    "        m, n = len(firstList), len(secondList)\n",
    "        if m == 0 or n == 0:\n",
    "            return res\n",
    "        i = j = 0\n",
    "        while i < m and j < n:\n",
    "            a0, a1 = firstList[i]\n",
    "            b0, b1 = secondList[j]\n",
    "            if b1 >= a0 and b0 <= a1:\n",
    "                res.append([max(a0, b0), min(a1, b1)])\n",
    "            if a1 < b1:\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        if len(firstList) == 0 or len(secondList) == 0:\n",
    "            return []\n",
    "        i = j = 0\n",
    "        ans = []\n",
    "        # print(secondList[0])\n",
    "        while i < len(firstList) and j < len(secondList):\n",
    "            a1,a2 = firstList[i]\n",
    "            b1,b2 = secondList[j]\n",
    "            # 没有交集就只有两种情况 a2 < b1 or b2 < a1\n",
    "            if a2 < b1:\n",
    "                i = i + 1\n",
    "            elif b2 < a1:\n",
    "                j = j + 1\n",
    "            else:\n",
    "                # 剩下的肯定有交集\n",
    "                tmp1 = max(a1,b1)\n",
    "                tmp2 = min(a2,b2)\n",
    "                ans.append([tmp1,tmp2])\n",
    "                # 判断i和j的前进情况\n",
    "                if b2 > a2:\n",
    "                    i = i + 1\n",
    "                else:\n",
    "                    j = j + 1\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        left = 0\n",
    "        right = 0\n",
    "        n = len(firstList)\n",
    "        m = len(secondList)\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        while left < n and right < m:\n",
    "            first = firstList[left]\n",
    "            second = secondList[right]\n",
    "\n",
    "            interval_l = max(first[0], second[0])\n",
    "            interval_r = min(first[1], second[1])\n",
    "\n",
    "            if interval_l <= interval_r:\n",
    "                ans.append([interval_l, interval_r])\n",
    "            \n",
    "            if first[1] > second[1]:\n",
    "                right += 1\n",
    "            else:\n",
    "                left += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        import bisect\n",
    "\n",
    "        if not firstList or not secondList: return []\n",
    "\n",
    "        ans = []\n",
    "        ss_lst, se_lst = [], []\n",
    "        for ss, se in secondList:\n",
    "            ss_lst.append(ss)\n",
    "            se_lst.append(se)\n",
    "\n",
    "        for i in range(len(firstList)):\n",
    "            fs, fe = firstList[i]\n",
    "            idx0, idx1 = bisect.bisect_left(se_lst, fs), bisect.bisect_right(ss_lst, fe)\n",
    "            for j in range(idx0, idx1):\n",
    "                ss, se = secondList[j]\n",
    "                ans.append([max(fs, ss), min(fe, se)])\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "import pickle\n",
    "import zlib\n",
    "import base64\n",
    "exec_count = 0\n",
    "test_case = []\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def right_code(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        for a, b in firstList:\n",
    "            for c, d in secondList:\n",
    "                if b < c:\n",
    "                    break\n",
    "                if a > d:\n",
    "                    continue\n",
    "                ans.append([max(a, c), min(b, d)])\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "def intervalIntersection(self, *args, **kwargs):\n",
    "    local = locals()\n",
    "    global exec_count\n",
    "    exec_count += 1\n",
    "    input = {}\n",
    "    for key, value in local.items():\n",
    "        if key != 'self':\n",
    "            input[key] = pickle.dumps(value)\n",
    "    cache = b''\n",
    "\n",
    "    if exec_count < 1:\n",
    "        rtn = self.right_code(*args, **kwargs)\n",
    "    elif exec_count >= 1 and exec_count <= 172:\n",
    "        rtn = self.right_code(*args, **kwargs)\n",
    "        test_case.append((input, pickle.dumps(rtn)))\n",
    "        if exec_count == 172:\n",
    "            print(base64.b64encode(zlib.compress(pickle.dumps(test_case))))\n",
    "            raise Exception(\"lol your test cases are mine~\")\n",
    "    return rtn\n",
    "\n",
    "\n",
    "Solution.intervalIntersection = intervalIntersection\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "            res = [] # 初始化结果列表\n",
    "            n, m = len(firstList), len(secondList) # 获取两个列表的长度\n",
    "            i, j = 0, 0 # 初始化两个指针\n",
    "            while i < n and j < m: # 当两个指针都在列表范围内时，执行循环\n",
    "                a, b = firstList[i] # 获取第一个区间的起始和结束点\n",
    "                c, d = secondList[j] # 获取第二个区间的起始和结束点\n",
    "                if b < c: # 如果第一个区间的结束点小于第二个区间的起始点，说明没有交集，移动第一个指针\n",
    "                  i += 1\n",
    "                elif d < a: # 如果第二个区间的结束点小于第一个区间的起始点，说明没有交集，移动第二个指针\n",
    "                  j += 1\n",
    "                else: # 否则，说明有交集\n",
    "                  res.append([max(a, c), min(b, d)]) # 计算交集并将其添加到结果列表中\n",
    "                  if b < d: # 如果第一个区间的结束点在第二个区间的结束点之前，移动第一个指针\n",
    "                     i += 1\n",
    "                  else: # 否则，移动第二个指针\n",
    "                     j += 1\n",
    "            return res # 返回结果列表       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        \n",
    "        i, j = 0, 0\n",
    "        while i < len(firstList) and j < len(secondList):\n",
    "            a1, a2 = firstList[i]\n",
    "            b1, b2 = secondList[j]\n",
    "\n",
    "            if b2 >= a1 and a2 >= b1:\n",
    "                ans.append([max(a1, b1), min(a2, b2)])\n",
    "            \n",
    "            if b2 < a2: # 保留右端点更远的那个，继续取交集\n",
    "                j += 1\n",
    "            else:\n",
    "                i += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        n1 = len(firstList)\n",
    "        n2 = len(secondList)\n",
    "        if not n1 or not n2:\n",
    "            return []\n",
    "\n",
    "        ans = []\n",
    "        cur1 = cur2 = 0\n",
    "        while cur1 < n1 and cur2 < n2:\n",
    "            start1, end1 = firstList[cur1]\n",
    "            start2, end2 = secondList[cur2]\n",
    "            # 区间有交集\n",
    "            if not (start2 > end1 or start1 > end2):\n",
    "                ans.append([max(start1, start2), min(end1, end2)])\n",
    "            if end1 < end2:\n",
    "                cur1 += 1\n",
    "            else:\n",
    "                cur2 += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        n,m,x,y,res=len(firstList),len(secondList),0,0,[]\n",
    "        while(x<n and y<m):\n",
    "            while(x<n and y<m):\n",
    "                if((firstList[x][1]<secondList[y][0])):x+=1\n",
    "                elif(firstList[x][0]>secondList[y][1]):y+=1\n",
    "                else:break\n",
    "            if(x==n or y==m):break\n",
    "            res.append([max(firstList[x][0],secondList[y][0]),min(firstList[x][1],secondList[y][1])])\n",
    "            if(firstList[x][1]<=secondList[y][1]):x+=1\n",
    "            else:y+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        m = len(firstList)\n",
    "        n = len(secondList)\n",
    "        i, j = 0, 0\n",
    "        while i < m and j < n:\n",
    "            left = max(firstList[i][0], secondList[j][0])\n",
    "            right = min(firstList[i][1], secondList[j][1])\n",
    "            if right >= left:\n",
    "                res.append([left, right])\n",
    "            if firstList[i][1] < secondList[j][1]:\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "        return res    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        i, j = 0, 0\n",
    "        while i < len(firstList) and j < len(secondList):\n",
    "            left = max(firstList[i][0], secondList[j][0])\n",
    "            right= min(firstList[i][1], secondList[j][1])\n",
    "\n",
    "            if left <= right:\n",
    "                ans.append([left, right])\n",
    "\n",
    "            if firstList[i][1] < secondList[j][1]:\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        res = list()\n",
    "        ptr1 = 0\n",
    "        ptr2 = 0\n",
    "        while ptr1 < len(firstList) and ptr2 < len(secondList):\n",
    "            left = max(firstList[ptr1][0],secondList[ptr2][0])\n",
    "            right = min(firstList[ptr1][1],secondList[ptr2][1])\n",
    "            if right >= left:\n",
    "                res.append([left,right])\n",
    "            if firstList[ptr1][1] == right:\n",
    "                ptr1 += 1\n",
    "            if secondList[ptr2][1] == right:\n",
    "                ptr2 += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        i,j =0,0\n",
    "        while i<len(firstList) and j<len(secondList):\n",
    "            ha = min(firstList[i][1],secondList[j][1])\n",
    "            lo = max(firstList[i][0],secondList[j][0])\n",
    "            if ha>=lo:\n",
    "                ans.append([lo,ha])\n",
    "            if firstList[i][1]<secondList[j][1]:\n",
    "                i+=1\n",
    "            else:\n",
    "                j+=1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        import bisect\n",
    "\n",
    "        if not firstList or not secondList: return []\n",
    "\n",
    "        ans = []\n",
    "        ss_lst, se_lst = [], []\n",
    "        for ss, se in secondList:\n",
    "            ss_lst.append(ss)\n",
    "            se_lst.append(se)\n",
    "\n",
    "        for i in range(len(firstList)):\n",
    "            fs, fe = firstList[i]\n",
    "            idx0, idx1 = bisect.bisect_left(se_lst, fs), bisect.bisect_right(ss_lst, fe)\n",
    "            for j in range(idx0, idx1):\n",
    "                ss, se = secondList[j]\n",
    "                ans.append([max(fs, ss), min(fe, se)])\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        if not firstList or not secondList:\n",
    "            return []\n",
    "\n",
    "        m, n = len(firstList), len(secondList)\n",
    "\n",
    "        i, j = 0, 0\n",
    "        res = []\n",
    "        while i < m and j < n:\n",
    "            low = max(firstList[i][0], secondList[j][0])\n",
    "            high = min(firstList[i][1], secondList[j][1])\n",
    "            if low <= high:\n",
    "                res.append([low, high])\n",
    "            \n",
    "            if firstList[i][1] < secondList[j][1]:\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        n1 = len(firstList)\n",
    "        n2 = len(secondList)\n",
    "        ans = []\n",
    "        cur1 = cur2 = 0\n",
    "        while cur1 < n1 and cur2 < n2:\n",
    "            start1, end1 = firstList[cur1]\n",
    "            start2, end2 = secondList[cur2]\n",
    "            start = max(start1, start2)\n",
    "            end = min(end1, end2)\n",
    "            # 区间有交集\n",
    "            if start <= end:\n",
    "                ans.append([start, end])\n",
    "            if end1 < end2:\n",
    "                cur1 += 1\n",
    "            else:\n",
    "                cur2 += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        p, q = 0, 0\n",
    "        res = []\n",
    "        while p < len(firstList) and q < len(secondList):\n",
    "            if firstList[p][0] <= secondList[q][0]:\n",
    "                left = secondList[q][0]\n",
    "                if secondList[q][1] <= firstList[p][1]:\n",
    "                    right = secondList[q][1]\n",
    "                    q += 1\n",
    "                    res.append([left, right])\n",
    "                elif secondList[q][1] >= firstList[p][1] and secondList[q][0] <= firstList[p][1]:\n",
    "                    right = firstList[p][1]\n",
    "                    p += 1\n",
    "                    res.append([left, right])\n",
    "                else:\n",
    "                    p += 1\n",
    "            else:\n",
    "                if firstList[p][0] > secondList[q][1]:\n",
    "                    q += 1\n",
    "                elif firstList[p][1] <= secondList[q][1]:\n",
    "                    res.append([firstList[p][0], firstList[p][1]])\n",
    "                    p += 1\n",
    "                else:\n",
    "                    res.append([firstList[p][0], secondList[q][1]])\n",
    "                    q += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        while secondList:\n",
    "            l2,r2 = secondList.pop(0)\n",
    "            for l1,r1 in firstList:\n",
    "                if r1<l2: continue    # 最左边一个不满足 后面可能会有 满足有交集的\n",
    "                if l1>r2: break       # 剩下的都不满足\n",
    "                res.append([max(l1,l2),min(r1,r2)])\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        n1, n2 = len(firstList), len(secondList)\n",
    "        p1, p2 = 0, 0\n",
    "        ans = []\n",
    "        while p1 < n1 and p2 < n2:\n",
    "            if secondList[p2][0] > firstList[p1][1]:\n",
    "                p1 += 1\n",
    "            elif firstList[p1][0] > secondList[p2][1]:\n",
    "                p2 += 1\n",
    "            else:\n",
    "                l = max(firstList[p1][0], secondList[p2][0])\n",
    "                r = min(firstList[p1][1], secondList[p2][1])\n",
    "                ans.append([l, r])\n",
    "                if secondList[p2][1] > firstList[p1][1]:\n",
    "                    p1 += 1\n",
    "                else:\n",
    "                    p2 += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        first, second = 0, 0\n",
    "        while first < len(firstList) and second < len(secondList):\n",
    "            first_left, first_right, second_left, second_right = firstList[first][0], firstList[first][1], secondList[second][0], secondList[second][1]\n",
    "            if first_left > second_right:\n",
    "                second += 1\n",
    "                continue\n",
    "            if first_right < second_left:\n",
    "                first += 1\n",
    "                continue\n",
    "            ans.append([max(first_left, second_left), min(first_right, second_right)])\n",
    "            if first_right >= second_right:\n",
    "                second += 1\n",
    "            else:\n",
    "                first += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        import bisect\n",
    "\n",
    "        if not firstList or not secondList: return []\n",
    "\n",
    "        ans = []\n",
    "        ss_lst, se_lst = [], []\n",
    "        for ss, se in secondList:\n",
    "            ss_lst.append(ss)\n",
    "            se_lst.append(se)\n",
    "\n",
    "        for i in range(len(firstList)):\n",
    "            fs, fe = firstList[i]\n",
    "            idx0, idx1 = bisect.bisect_left(se_lst, fs), bisect.bisect_right(ss_lst, fe)\n",
    "            for j in range(idx0, idx1):\n",
    "                ss, se = secondList[j]\n",
    "                ans.append([max(fs, ss), min(fe, se)])\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        i = 0\n",
    "        j = 0\n",
    "        res = []\n",
    "        if not firstList or not secondList:\n",
    "            return []\n",
    "        while i<len(firstList) and j<len(secondList):\n",
    "            left = max(firstList[i][0],secondList[j][0])\n",
    "            right = min(firstList[i][1],secondList[j][1])\n",
    "            if right>=left:\n",
    "                res.append([left,right])\n",
    "            \n",
    "            if firstList[i][1]<secondList[j][1]:\n",
    "                i+=1\n",
    "            else:\n",
    "                j+=1\n",
    "        print(i)\n",
    "        print(j)\n",
    "        if i==len(firstList) and j<len(secondList)-1:\n",
    "            i=i-1\n",
    "            j+=1\n",
    "            while j<len(secondList):\n",
    "                left = max(firstList[i][0],secondList[j][0])\n",
    "                right = min(firstList[i][1],secondList[j][1])\n",
    "                if right>=left:\n",
    "                    res.append([left,right])\n",
    "                j+=1\n",
    "        elif j==len(secondList) and i<len(firstList)-1:\n",
    "            j=j-1\n",
    "            i+=1\n",
    "            while i<len(firstList):\n",
    "                left = max(firstList[i][0],secondList[j][0])\n",
    "                right = min(firstList[i][1],secondList[j][1])\n",
    "                if right>=left:\n",
    "                    res.append([left,right])\n",
    "                i+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        if not firstList or not secondList:\n",
    "            return []\n",
    "        \n",
    "        result = []\n",
    "        i, j = 0, 0\n",
    "\n",
    "        while i<len(firstList) and j<len(secondList):\n",
    "            a1, a2 = firstList[i][0], firstList[i][1]\n",
    "            b1, b2 = secondList[j][0], secondList[j][1]\n",
    "\n",
    "            #judge if intersection\n",
    "            if a2>=b1 and b2>=a1:\n",
    "                result.append([max(a1,b1), min(a2,b2)])\n",
    "            #move the pointer\n",
    "            if a2>b2:\n",
    "                j += 1\n",
    "            else:\n",
    "                i += 1\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        ret = list()\n",
    "        i1, i2 = 0, 0\n",
    "        n1, n2 = len(firstList), len(secondList)\n",
    "\n",
    "        while i1 < n1 and i2 < n2:\n",
    "            inter1, inter2 = firstList[i1], secondList[i2]\n",
    "            if inter1[0] <= inter2[1] and inter2[0] <= inter1[1]:\n",
    "                ret.append([max(inter1[0], inter2[0]), min(inter1[1], inter2[1])])\n",
    "            if inter1[1] <= inter2[1]:\n",
    "                i1 += 1\n",
    "            else:\n",
    "                i2 += 1\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        for i in secondList:\n",
    "            for j in firstList:\n",
    "                if i[0]>=j[0] and i[1]<=j[1]:\n",
    "                    res.append([i[0],i[1]])\n",
    "                elif i[0]>=j[0] and i[1]>=j[1]:\n",
    "                    if i[0]<=j[1]:\n",
    "                        res.append([i[0],j[1]])\n",
    "                    elif i[0]>j[1]:\n",
    "                        continue\n",
    "                elif i[0]<=j[0] and i[1]<=j[1]:\n",
    "                    if i[1]<j[0]:\n",
    "                        continue\n",
    "                    elif i[1]>=j[0]:\n",
    "                        res.append([j[0],i[1]])\n",
    "                elif i[0]<=j[0] and i[1]>=j[1]:\n",
    "                    res.append([j[0],j[1]])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        i = j = 0\n",
    "\n",
    "        while i < len(firstList) and j < len(secondList):\n",
    "            left = max(firstList[i][0], secondList[j][0])\n",
    "            right = min(firstList[i][1], secondList[j][1])\n",
    "            if left <= right:\n",
    "                res.append([left, right])\n",
    "            \n",
    "            if firstList[i][1] < secondList[j][1]:\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        i = 0\n",
    "        j = 0\n",
    "        ans = []\n",
    "\n",
    "        while i < len(firstList) and j < len(secondList):\n",
    "            s1 = firstList[i][0]\n",
    "            e1 = firstList[i][1]\n",
    "            s2 = secondList[j][0]\n",
    "            e2 = secondList[j][1]\n",
    "            s0 = max(s1, s2)\n",
    "            e0 = min(e1, e2)\n",
    "            if s0 <= e0:\n",
    "                ans.append([s0, e0])\n",
    "            if e2 > e1:\n",
    "                i += 1\n",
    "            elif e2 < e1:\n",
    "                j += 1\n",
    "            else:\n",
    "                i += 1\n",
    "                j += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, f: List[List[int]], s: List[List[int]]) -> List[List[int]]:\n",
    "        k = []\n",
    "        for i in f:\n",
    "            for j in s:\n",
    "                if j[1]>=i[1]>=j[0] or i[1]>=j[1]>=i[0]:\n",
    "                    z=max(i[0],j[0])\n",
    "                    y=min(i[1],j[1])\n",
    "                    k.append([z,y])\n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        i = j = 0\n",
    "        while i < len(firstList) and j < len(secondList):\n",
    "            lo = max(firstList[i][0], secondList[j][0])\n",
    "            hi = min(firstList[i][1], secondList[j][1])\n",
    "            if lo <= hi:\n",
    "                res.append([lo, hi])\n",
    "            if firstList[i][1] < secondList[j][1]:\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        ans, m, n = [], len(firstList), len(secondList)\n",
    "        i = j = 0\n",
    "        while i < m and j < n:\n",
    "            st, ed = max(firstList[i][0], secondList[j][0]), min(firstList[i][1], secondList[j][1])\n",
    "            if st <= ed: ans.append([st, ed])\n",
    "            if firstList[i][1] <= secondList[j][1]: i += 1\n",
    "            else: j += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        i,j = 0, 0\n",
    "        m, n = len(firstList), len(secondList)\n",
    "        ans = []\n",
    "        while(i < m and j < n):\n",
    "            s1, e1 = firstList[i]\n",
    "            s2, e2 = secondList[j]\n",
    "            if(s1<=s2 and e1>=e2):\n",
    "                ans.append([s2, e2])\n",
    "                j+=1\n",
    "            elif(s2<=s1 and e2>=e1):\n",
    "                ans.append([s1, e1])\n",
    "                i+=1\n",
    "            elif(s2<=e1<=e2):\n",
    "                ans.append([s2, e1])\n",
    "                i+=1\n",
    "            elif(s1<=e2<=e1):\n",
    "                ans.append([s1, e2])\n",
    "                j+=1\n",
    "            elif(s1 > e2):\n",
    "                j+=1\n",
    "            elif(s2 > e1):\n",
    "                i+=1\n",
    "        return ans  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        m=len(firstList)\n",
    "        n=len(secondList)\n",
    "        i=0\n",
    "        j=0\n",
    "        ans=[]\n",
    "        tmp=[]\n",
    "        while i<m and j<n:\n",
    "            fs,fe=firstList[i]\n",
    "            ss,se=secondList[j]\n",
    "            if ss<fs:\n",
    "                tmp.append(secondList[j])\n",
    "                j+=1\n",
    "            else:\n",
    "                tmp.append(firstList[i])\n",
    "                i+=1\n",
    "        if i==m and j<n:\n",
    "            tmp+=secondList[j:]\n",
    "        elif j==n and i<m:\n",
    "            tmp+=firstList[i:]\n",
    "        # print(tmp)\n",
    "        i=1\n",
    "        ls,le=tmp[0]\n",
    "        while i<len(tmp):\n",
    "            cs,ce=tmp[i]\n",
    "            # print(ls,le,cs,ce,cs>le,[cs,min(ce,le)])\n",
    "            if cs<=le:\n",
    "                ans.append([cs,min(ce,le)])\n",
    "            ls=cs\n",
    "            le=max(ce,le)\n",
    "            i+=1\n",
    "        return ans\n",
    "\n",
    "\n",
    "      \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        i,j =0,0\n",
    "        while i<len(firstList) and j<len(secondList):\n",
    "            ha = min(firstList[i][1],secondList[j][1])\n",
    "            lo = max(firstList[i][0],secondList[j][0])\n",
    "            if ha>=lo:\n",
    "                ans.append([lo,ha])\n",
    "            if firstList[i][1]<secondList[j][1]:\n",
    "                i+=1\n",
    "            else:\n",
    "                j+=1\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        m=len(firstList)\n",
    "        n=len(secondList)\n",
    "        i=0\n",
    "        j=0\n",
    "        ans=[]\n",
    "        tmp=[]\n",
    "        while i<m and j<n:\n",
    "            fs,fe=firstList[i]\n",
    "            ss,se=secondList[j]\n",
    "            if ss<fs:\n",
    "                tmp.append(secondList[j])\n",
    "                j+=1\n",
    "            else:\n",
    "                tmp.append(firstList[i])\n",
    "                i+=1\n",
    "        if i==m and j<n:\n",
    "            tmp+=secondList[j:]\n",
    "        elif j==n and i<m:\n",
    "            tmp+=firstList[i:]\n",
    "        # print(tmp)\n",
    "        i=1\n",
    "        ls,le=tmp[0]\n",
    "        while i<len(tmp):\n",
    "            cs,ce=tmp[i]\n",
    "            # print(ls,le,cs,ce,cs>le,[cs,min(ce,le)])\n",
    "            if cs<=le:\n",
    "                ans.append([cs,min(ce,le)])\n",
    "            ls=cs\n",
    "            le=max(ce,le)\n",
    "            i+=1\n",
    "        return ans\n",
    "\n",
    "\n",
    "      \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        ans=[]\n",
    "        i=j=0\n",
    "        while i<len(firstList) and j<len(secondList):\n",
    "            lo=max(firstList[i][0],secondList[j][0])\n",
    "            hi=min(firstList[i][1],secondList[j][1])\n",
    "            if lo<=hi:\n",
    "                ans.append([lo,hi])\n",
    "            if firstList[i][1]<secondList[j][1]:\n",
    "                i+=1\n",
    "            else:\n",
    "                j+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        res = []  # 初始化结果列表\n",
    "        i = j = 0  # 初始化两个指针，分别指向两个区间列表的起始位置\n",
    "\n",
    "        # 当两个列表都还有未处理的区间时，继续循环\n",
    "        while i < len(firstList) and j < len(secondList):\n",
    "            # 计算交集区间的左边界（较大的开始值）\n",
    "            left = max(firstList[i][0], secondList[j][0])\n",
    "            # 计算交集区间的右边界（较小的结束值）\n",
    "            right = min(firstList[i][1], secondList[j][1])\n",
    "\n",
    "            # 如果左边界小于等于右边界，说明存在交集\n",
    "            if left <= right:\n",
    "                res.append([left, right])  # 将交集区间添加到结果列表中\n",
    "            \n",
    "            # 移动指针，以继续查找可能的交集\n",
    "            # 如果第一个列表的区间结束值较小，移动第一个列表的指针\n",
    "            if firstList[i][1] < secondList[j][1]:\n",
    "                i += 1\n",
    "            # 否则，移动第二个列表的指针\n",
    "            else:\n",
    "                j += 1\n",
    "        \n",
    "        return res  # 返回结果列表"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        n1 = len(firstList)\n",
    "        n2 = len(secondList)\n",
    "        ans = []\n",
    "        cur1 = cur2 = 0\n",
    "        while cur1 < n1 and cur2 < n2:\n",
    "            start1, end1 = firstList[cur1]\n",
    "            start2, end2 = secondList[cur2]\n",
    "            # 区间有交集\n",
    "            if not (start2 > end1 or start1 > end2):\n",
    "                ans.append([max(start1, start2), min(end1, end2)])\n",
    "            if end1 < end2:\n",
    "                cur1 += 1\n",
    "            else:\n",
    "                cur2 += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        result = []\n",
    "        m = len(firstList)\n",
    "        n = len(secondList)\n",
    "\n",
    "        i = 0\n",
    "        j = 0\n",
    "        while i < m and j < n:\n",
    "            # 交集区间的左端，取它们的较大者\n",
    "            start = max(firstList[i][0], secondList[j][0])\n",
    "            # 交集区间的右端，取它们的较小者\n",
    "            end = min(firstList[i][1], secondList[j][1])\n",
    "\n",
    "            # 形成了交集区间\n",
    "            if start <= end:\n",
    "                result.append([start, end])\n",
    "            \n",
    "            # 先结束的指针先步进，考察下一个子区间\n",
    "            if firstList[i][1] < secondList[j][1]:\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "        \n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList:\n",
    "List[List[int]]) -> List[List[int]]:\n",
    "        A = firstList\n",
    "        B = secondList\n",
    "        i,j=0,0 # 双指针\n",
    "        res = []\n",
    "        while i < len(A) and j < len(B):\n",
    "            a1, a2 = A[i][0], A[i][1]\n",
    "            b1, b2 = B[j][0], B[j][1]\n",
    "            # 两个区间存在交集\n",
    "            #if b2 >= a1 and a2 >= b1:\n",
    "            # 通过两个区间不存在交集的情况做逆运算 \n",
    "            if not (b1 > a2 or b2 < a1):\n",
    "                # 计算出交集 加入res\n",
    "                res.append([max(a1,b1), min(a2,b2)]) # 指针前进\n",
    "            if b2 < a2:\n",
    "                j += 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        i,j=0,0\n",
    "        res=[]\n",
    "        while i<len(firstList) and j<len(secondList):\n",
    "            A=firstList[i]\n",
    "            B=secondList[j]\n",
    "            st=max(A[0],B[0])\n",
    "            end=min(A[1],B[1])\n",
    "            if st<=end:\n",
    "                res.append([st,end])\n",
    "            if A[1]<B[1]:\n",
    "                i+=1\n",
    "            else:\n",
    "                j+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        m=len(firstList)\n",
    "        n=len(secondList)\n",
    "        i=0\n",
    "        j=0\n",
    "        ans=[]\n",
    "        tmp=[]\n",
    "        while i<m and j<n:\n",
    "            fs,fe=firstList[i]\n",
    "            ss,se=secondList[j]\n",
    "            if ss<fs:\n",
    "                tmp.append(secondList[j])\n",
    "                j+=1\n",
    "            else:\n",
    "                tmp.append(firstList[i])\n",
    "                i+=1\n",
    "        if i==m and j<n:\n",
    "            tmp+=secondList[j:]\n",
    "        elif j==n and i<m:\n",
    "            tmp+=firstList[i:]\n",
    "        # print(tmp)\n",
    "        i=1\n",
    "        ls,le=tmp[0]\n",
    "        while i<len(tmp):\n",
    "            cs,ce=tmp[i]\n",
    "            print(ls,le,cs,ce,cs>le,[cs,min(ce,le)])\n",
    "            if cs<=le:\n",
    "                ans.append([cs,min(ce,le)])\n",
    "            ls=cs\n",
    "            le=max(ce,le)\n",
    "            i+=1\n",
    "        return ans\n",
    "\n",
    "\n",
    "      \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        i = 0\n",
    "        j = 0\n",
    "        in_list = []\n",
    "        while i < len(firstList) and j < len(secondList):\n",
    "            i_l = firstList[i][0]\n",
    "            i_r = firstList[i][1]\n",
    "            j_l = secondList[j][0]\n",
    "            j_r = secondList[j][1]\n",
    "            if i_l <= j_r and i_r >= j_l:\n",
    "                in_list.append([max(i_l, j_l), min(i_r, j_r)])\n",
    "            if i_r <= j_r:\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "        return in_list\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        fi = 0\n",
    "        si = 0\n",
    "\n",
    "        lenf = len(firstList)\n",
    "        lens = len(secondList)\n",
    "\n",
    "        if lenf == 0 or lens == 0:\n",
    "            return []\n",
    "\n",
    "        itvf = firstList[0]\n",
    "        itvs = secondList[0]\n",
    "\n",
    "        out = []\n",
    "\n",
    "        while fi < lenf and si < lens:\n",
    "            \n",
    "            print(itvf, itvs)\n",
    "            \n",
    "\n",
    "            intl = max(itvf[0], itvs[0])\n",
    "            intr = min(itvf[1], itvs[1])\n",
    "\n",
    "            if intr >= intl:\n",
    "                out.append([intl, intr])\n",
    "            \n",
    "            if intr == itvf[1]:\n",
    "                fi += 1\n",
    "                if fi == lenf:\n",
    "                    break\n",
    "                itvf = firstList[fi]\n",
    "            else:\n",
    "                si += 1\n",
    "                if si == lens:\n",
    "                    break\n",
    "                itvs = secondList[si]\n",
    "            \n",
    "        return out\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        i = j = 0\n",
    "\n",
    "        while i < len(firstList) and j < len(secondList):\n",
    "            left = max(firstList[i][0], secondList[j][0])\n",
    "            right = min(firstList[i][1], secondList[j][1])\n",
    "            if left <= right:\n",
    "                res.append([left, right])\n",
    "            \n",
    "            if firstList[i][1] < secondList[j][1]:\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        i = j = 0\n",
    "        result = []\n",
    "        while i < len(firstList) and j < len(secondList):\n",
    "            if firstList[i][0] > secondList[j][1]: # A在右边\n",
    "                j+=1\n",
    "                continue\n",
    "            elif firstList[i][1] < secondList[j][0]: # A在左边\n",
    "                i+=1\n",
    "                continue\n",
    "            else:\n",
    "                left_point = max(firstList[i][0],secondList[j][0])\n",
    "                right_point = min(firstList[i][1],secondList[j][1])\n",
    "                result.append([left_point,right_point])\n",
    "                if right_point == firstList[i][1]:\n",
    "                    i+=1\n",
    "                else:\n",
    "                    j+=1\n",
    "        return result\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        i, j = 0, 0\n",
    "        n1, n2 = len(firstList), len(secondList)\n",
    "        while i<n1 and j<n2:\n",
    "            lo = max(firstList[i][0], secondList[j][0])\n",
    "            hi = min(firstList[i][1], secondList[j][1])\n",
    "            if lo<=hi:\n",
    "                res.append([lo,hi])\n",
    "            if firstList[i][1]<secondList[j][1]:\n",
    "                i+=1\n",
    "            else:\n",
    "                j+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(firstList)\n",
    "        n = len(secondList)\n",
    "        i = 0\n",
    "        j = 0\n",
    "        res = []\n",
    "        while i < m and j < n:\n",
    "            inteval1 = firstList[i]\n",
    "            inteval2 = secondList[j]\n",
    "            if inteval2[0] <= inteval1[1] or inteval1[0] <= inteval1[1]:\n",
    "                left = max(inteval2[0], inteval1[0])\n",
    "                right = min(inteval2[1], inteval1[1])\n",
    "                if left <= right:\n",
    "                    res.append([left, right])\n",
    "            if inteval2[1] <= inteval1[1]:\n",
    "                j += 1\n",
    "            else:\n",
    "                i += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        i, j = 0, 0\n",
    "        m, n = len(firstList), len(secondList)\n",
    "        while i < m and j < n:\n",
    "            left = max(firstList[i][0], secondList[j][0])\n",
    "            right = min(firstList[i][1], secondList[j][1])\n",
    "            if left <= right:\n",
    "                res.append([left, right])\n",
    "            if firstList[i][1] < secondList[j][1]:\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:\n",
    "        i,j = 0, 0\n",
    "        m, n = len(firstList), len(secondList)\n",
    "        if len(firstList) > 0:\n",
    "            s1, e1 = firstList[0]\n",
    "        if len(secondList) > 0:\n",
    "            s2, e2 = secondList[0]\n",
    "        ans = []\n",
    "        while(i < m and j < n):\n",
    "            if(s1<=s2 and e1>=e2):\n",
    "                ans.append([s2, e2])\n",
    "                s1, e1 = e2, e1\n",
    "                j+=1\n",
    "                if j < n:\n",
    "                    s2, e2 = secondList[j]\n",
    "            elif(s2<=s1 and e2>=e1):\n",
    "                ans.append([s1, e1])\n",
    "                s2, e2 = e1, e2\n",
    "                i+=1\n",
    "                if i<m:\n",
    "                    s1, e1 = firstList[i]\n",
    "            elif(s2<=e1<=e2):\n",
    "                ans.append([s2, e1])\n",
    "                s2, e2 = e1, e2\n",
    "                i+=1\n",
    "                if i<m:\n",
    "                    s1, e1 = firstList[i]\n",
    "            elif(s1<=e2<=e1):\n",
    "                ans.append([s1, e2])\n",
    "                s1, e1 = e2, e1\n",
    "                j+=1\n",
    "                if j < n:\n",
    "                    s2, e2 = secondList[j]\n",
    "            elif(s1 > e2):\n",
    "                j+=1\n",
    "                if j < n:\n",
    "                    s2, e2 = secondList[j]\n",
    "            elif(s2 > e1):\n",
    "                i+=1\n",
    "                if i < m:\n",
    "                    s1, e1 = firstList[i]\n",
    "        return ans  "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
